// Created by Acer on 2/22 022.
#ifndef ANDROIDARCHITECT02_BST_H
#define ANDROIDARCHITECT02_BST_H

#include <iostream>

template<class K, class V>
struct TreeNode {
public:
    // 复制一个点。避免pNode被销毁，找不到关联关系。
    TreeNode(TreeNode<K, V> *pNode) {
        this->left = pNode->left;
        this->right = pNode->right;
        this->key = pNode->key;
        this->value = pNode->value;
    }

    TreeNode<K,V>* left  = NULL;
    TreeNode<K,V>* right = NULL;
    K key;
    V value;

    TreeNode(K key, V value) {
        this->right = NULL;
        this->left = NULL;
        this->key = key;
        this->value = value;
    }
};

template<class K, class V>
class BST {
     TreeNode<K,V>* root; // 根节点
     int count; // 个数

public:
    BTS() { // 构造函数，析构函数
        root = NULL;
        count = 0;
    }
    ~BTS(){
    }

    // 新增/修改
    void put(K key, V value) {
        root = addNode(root, key, value);
    }
    V* get(K key){
        // TODO 1.是否包含，包含了采取查找。没包含就不查找
        // 2. 没找到返回V*， int *value = bst->get(100); if(value==NULL) { ...}
        return NULL;
    }
    int size(){
        return count;
    }
    // 删除操作。
    void remove(K key) {
        // 分情况处理，移除非叶子节点，也要返回指针。
        root = removeNode(root, key);
    }

    bool contains(K key) { // 是否包含
       TreeNode<K, V> *node = root; // 拿到根节点

       while (node) {
           if (node->key == key) {
               return node->value; // 包含
           } else if (node->key > key) { // 大，进入左边子树
               node = node->left;
           } else { // 进入右边子树
               node = node->right;
           }
       }
       return false;
    }

private:
    // 找左边的后进Node（左边树 最大的值）
    TreeNode<K,V>* maximum(TreeNode<K,V>* pNode) {
        // 不断地往右边找，直到找到右边为空的节点，就找到了最大值。
        if(pNode->right == null) {
            return pNode; // 找到了
        }
        return maximum(pNode->right); // 不断往右边找。
    }

    // 找到升级了的点，删除。
    TreeNode<K,V>* deleteMax(TreeNode<K,V>* pNode) {
        if(pNode->right == null) {
            // 保存左边分支。
            TreeNode<K,V>* left = pNode->left;
            delete (pNode); // 删除 升级的节点。
            count--;
            return left; // 被删除点，左边的分支。要保留。
        }
        // 不断地找，直到找到删除。
        pNode->right = deleteMax(pNode->right);
        return pNode;
    }


    // 删除节点
    TreeNode<K,V>* removeNode(TreeNode<K,V>* pNode, K key) {
        // 递归结束
        if(pNode == NULL) return NULL;

        if(pNode->key > key) { // 往左边删除
            pNode->left = removeNode(pNode->left, key);
        } else if() { // 往右边删除
            pNode->right = removeNode(pNode->right, key);
        } else { // key相等（找到了）。执行删除
            count --;
            if(pNode->left == NULL && pNode->right == NULL) { // 无叶子结点，左右都为空
                delete pNode;
                return NULL;
            } else if(pNode->right == NULL) {
                // 右边为空，把左边放上去。
                // 左节点不为空, 左边的比父节点小。可以直接将左节点 替代当前删除的节点。
                TreeNode<K,V>* left = pNode->left;
                delete pNode;
                return left; // 避免pNode被析构了，找不到left。
            } else if(pNode->left == NULL) { // 右节点不为空
                // 左边为空，把右边放上去。
                TreeNode<K,V>* right = pNode->right;
                delete pNode;
                return right;
            } else { // 左右子树，都不为空的情况。
                // 找一个节点代替它。让树继续满足二叉搜索树。
                // 从左边找最大值来替代，或者从右边找最小值。缓存Node。
                TreeNode<K,V>* successor = new TreeNode<K, V>(maximum(pNode->left));
                // 原来的左节点，作为新根节点的左节点；原来的右节点，作为新根节点的右节点。
                // successor->left  = pNode->left;
                successor->left  = deleteMax(pNode->left); // 删除升级为根节点的 节点。
                count++; // 并没有删除升级的点，所以此处count要 +1

                successor->right = pNode->right;
                delete (pNode); // 删除当前节点。
                return successor;
            }
        }
    }

    // 返回新建的节点，与节点递归比较。
    TreeNode<K,V>* addNode(TreeNode<K,V>* pNode, K key, V value) {
        if(pNode == NULL) {
            count ++;
            return new TreeNode<K,V>(key, value); // 新建子节点（根节点 或叶子结点）
        }

        if(pNode->key > key){
            // 小。插入左边, 递归调用。返回的节点作为左子树。
            pNode->left = addNode(pNode->left, key, value);
        } else if(pNode->key < key){
            // 大：插入右边, 递归调用。返回的节点作为右子树。
            pNode->right = addNode(pNode->right, key, value);
        } else {
            // key相等，替换值value
            pNode->value = value;
        }
        return pNode;
    }

    // 中序遍历
    void inOrderTraverse(TreeNode<K, V> *pNode, void (*pFunction)(K, V)) {
        if (pNode == NULL) {
            return; // 到底了。
        }
        inOrderTraverse(pNode->left, pFunction); // 递归：先遍历左边
        pFunction(pNode->key, pNode->value);     // 访问自身
        inOrderTraverse(pNode->right, pFunction); // 遍历右边
    }
};


#endif //ANDROIDARCHITECT02_BST_H
